/**
 * @author: yu
 * @description: 合并两个有序链表
 * @create: 2025/04/06 17:38
 */
public class _021_mergeTwoLists {
    /**
     * Definition for singly-linked list.
     */
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    // 将原 Solution 类中的方法提取出来，修改类名
    public static ListNode mergeLists(ListNode head1, ListNode head2) {
        // 特判
        if (head1 == null || head2 == null) {
            return head1 == null ? head2 : head1;
        }
        ListNode head = head1.val <= head2.val ? head1 : head2;
        ListNode curr1 = head.next;
        ListNode curr2 = head == head1 ? head2 : head1;
        ListNode pre = head;
        while (curr1 != null && curr2 != null) {
            if (curr1.val <= curr2.val) {
                pre.next = curr1;
                curr1 = curr1.next;
            } else {
                pre.next = curr2;
                curr2 = curr2.next;
            }
            pre = pre.next;
        }
        pre.next = curr1 != null ? curr1 : curr2;
        return head;
    }

    // 辅助方法：用于打印链表
    public static void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // 创建第一个有序链表 1 -> 2 -> 4
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(4);

        // 创建第二个有序链表 1 -> 3 -> 4
        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(3);
        head2.next.next = new ListNode(4);

        ListNode mergedHead = mergeLists(head1, head2);

        // 打印合并后的链表
        printList(mergedHead);
    }
}